/*
Interleaving String My Submissions Question Solution
Total Accepted: 37531 Total Submissions: 179029 Difficulty: Hard
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Show Tags


*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/
typedef __int32 uint32_t;


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


class Solution {

public:
	bool dp[101][101];
	bool isInterleave(string s1, string s2, string s3) {
		
		int len1 = s1.size();
		int len2 = s2.size();
		int len3 = s3.size();

		if (len1+len2 != len3)
		{
			return false;
		}

		memset(dp, false, sizeof(bool)* 101 * 101);

		dp[0][0] = true;

		for (int i = 1; i <= len1; i++)
		{
			if (s1[i - 1] == s3[i - 1])
				dp[i][0] = true;
			else
			{
				break;
			}

		}

		for (int j = 1; j <= len2; j++)
		{
			if (s2[j - 1] == s3[j - 1])
				dp[0][j] = true;
			else
			{
				break;
			}
		}

		int k;

		for (int i = 1; i <= len1; i++)
		{
			for (int j = 1; j <= len2; j++)
			{
				k = i + j;
				if (s1[i - 1] == s3[k - 1])
					dp[i][j] = dp[i - 1][j] || dp[i][j];
				if (s2[j - 1] == s3[k - 1])
					dp[i][j] = dp[i][j - 1] || dp[i][j];
			}

		}
		return dp[len1][len2];


	}
};


int main(int argc, char* argv[])
{

	string s1 = "", s2 = "b", s3="b";
	

	int temp;
	Solution s;

	cout << "The reverse: " << s.isInterleave(s1,s2,s3)<< endl;






	system("pause");
	return 0;
}